package com.amado.course21BinaryTree;

public class BinaryTreeService {
	private Node root = null;

	BinaryTreeService() {

	}

	/**
	 * 插入
	 * 
	 * @param value
	 *            值
	 */
	public void insert(int value) {
		String message = "插入成功";
		Node node = new Node(value);
		// 为根节点为空时
		if (root == null) {
			root = node;
		} else {
			Node current = root;
			Node parent = null;
			while (true) {
				// 值少于当前节点
				if (value < current.getValue()) {
					parent = current;
					current = current.getLeft();
					if (current == null) {
						parent.setLeft(node);
						break;
					}
					// 值大于当前节点
				} else if (value > current.getValue()) {
					parent = current;
					current = current.getRight();
					if (current == null) {
						parent.setRight(node);
						break;
					}
				} else {
					message = "二叉树中存在相同的值";
					break;
				}
			}
		}
		System.out.println(message);
	}

	/**
	 * 中序遍历<br>
	 * 1.中序遍历左子树<br>
	 * 2.输出根结点<br>
	 * 3.中序遍历右子树<br>
	 * 
	 * @param node
	 */
	private void middleOrderIntertor(Node node) {
		if (node == null) {
			return;
		}
		middleOrderIntertor(node.getLeft());
		System.out.print(node.getValue()+"\t");
		middleOrderIntertor(node.getRight());
	}

	/**
	 * 先序遍历<br>
	 * 1.输出根结点<br>
	 * 2.先序遍历左子树<br>
	 * 3.先序遍历右子树
	 * 
	 * @param node
	 */
	private void beforeOrderIntertor(Node node) {
		if (node == null) {
			return;
		}
		System.out.print(node.getValue()+"\t");
		beforeOrderIntertor(node.getLeft());
		beforeOrderIntertor(node.getRight());
	}

	/**
	 * 后序遍历<br>
	 * 1.后序遍历左子树<br>
	 * 2.后序遍历右子树<br>
	 * 3.输出根结点<br>
	 * 
	 * @param node
	 */
	private void endOrderIntertor(Node node) {
		if (node == null) {
			return;
		}
		endOrderIntertor(node.getRight());
		System.out.print(node.getValue()+"\t");
		endOrderIntertor(node.getLeft());
	}

	public static void main(String[] args) {
		BinaryTreeService treeService = new BinaryTreeService();
		treeService.insert(50);
		treeService.insert(30);
		treeService.insert(36);
		treeService.insert(76);
		treeService.insert(45);
		treeService.insert(65);
		treeService.insert(58);
		treeService.insert(88);
		treeService.insert(18);
		treeService.insert(29);
		treeService.insert(10);
		treeService.insert(81);
		treeService.insert(99);
		System.out.println("先序遍历");
		treeService.beforeOrderIntertor(treeService.root);
		System.out.println("\n中序遍历");
		treeService.middleOrderIntertor(treeService.root);
		System.out.println("\n后序遍历");
		treeService.endOrderIntertor(treeService.root);
	}
}
